1 def suffix_array(s): 2     return [rank for suffix, rank in sorted((s[i:], i) for i in range(len(s)))] 3  4 def lcp_array(s): 5      6     sa = suffix_array(s) 7     n = len(s) 8     k = 0 9     lcp = [0] * n10     rank = [0] * n11     for i in range(n):12         rank[sa[i]] = i13         14     for i in range(n):15         if rank[i] == n-1:16             k = 017             continue18         j = sa[rank[i] + 1]19         while i + k < n and j + k < n and s[i + k] == s[j + k]:20             k += 121         lcp[rank[i]+1] = k;22         if k:23             k -= 124             25     return lcp